import java.util.Arrays;

public class java001 {
    public static void main(String[] args) {
       int[] a={1,3,6,5,2,7,10,9,8};
       insertSort(a);
        System.out.println("------------------");
       shellSort(a);
    }
    //插入排序--------------------------------------------
    /*一个数组从他的第二位开始取，取得值与前面的值比较比取值大的向后移动一位直到遇见比之小的就插入*/
    public static void insertSort(int[] a){
      for (int i=1;i<a.length;i++){
          for (int j=0;j<i;j++){
              if(a[i]<a[j]){
                  int temp=a[i];
                  for (int n=i-1;n>=j;n--){
                      a[n+1]=a[n];
                  }
                  a[j]=temp;
                  System.out.println(Arrays.toString(a));
              }
          }
      }
    }
    //希尔排序----------------------------------------------
    //插入排序的特殊操作按下标的一定增量来分组进行插入操作，
    public static void shellSort(int[] a){
      int gap=a.length/2;
      while (gap>=1) {
          for (int i = 0; i < a.length; i++) {
              if (i + gap >= a.length) {
                  break;
              } else if (a[i] > a[i + gap]) {
                  swap(a, i, i + gap);
              }
          }
          gap=gap/2;
          System.out.println(Arrays.toString(a));
      }
    }
    public static void swap(int[] a,int i,int j){
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
}
